package tree2;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Stack;

/**
 * 2-3 Tree for indexing document.
 * 
 * @author channisa
 * 
 */
public class Tree implements Serializable {
	/**
	 * root of tree
	 */
	private Node root;

	/**
	 * to trace parent from root to the node that will be search finding pattern
	 */
	private Stack<Node> stack;

	/**
	 * to count value that will be inserted
	 */
	private int jumVal;

	/**
	 * constructor
	 * 
	 * @param root
	 */
	public Tree(Node root) {
		this.root = root;
		this.jumVal = 1;
	}

	/**
	 * get root of the tree
	 * 
	 * @return root of the tree
	 */
	public Node getRoot() {
		return root;
	}

	/**
	 * set root of the tree
	 * 
	 * @param node
	 *            root
	 */
	public void setRoot(Node root) {
		this.root = root;
	}

	/**
	 * get the value that has been inserted to the tree
	 * 
	 * @return count of value
	 */
	public int getJumVal() {
		return jumVal;
	}

	/**
	 * finding x
	 * 
	 * @param x
	 *            value that will be found
	 * @return Node, weather its consist x or not. If not leaf node chose -> the
	 *         x must be consist in the node.
	 */
	public Node trace(int x) {
		stack = new Stack<Node>();
		Node current = this.root;
		while (!current.isLeaf() && current.getSubLeft().getKey() != x) {
			stack.push(current);
			if (current.getSubRight() != null
					&& current.getSubRight().getKey() != x) {
				if (x < current.getSubLeft().getKey()) {
					current = current.getNode_left();
				} else if (x > current.getSubRight().getKey()) {
					current = current.getNode_right();
				} else {
					current = current.getNode_middle();
				}
			} else {
				if (x < current.getSubLeft().getKey()) {
					current = current.getNode_left();
				} else {
					current = current.getNode_middle();
				}
			}

		}
		return current;
	}

	/**
	 * finding x value in the tree
	 * 
	 * @param x
	 *            value that will be searched
	 * @return NULL if fail to find subject. If success return Node contain x.
	 */
	public Node search(int x) {
		Node hasil = trace(x);
		if (hasil.getSubLeft().getKey() == x
				|| hasil.getSubRight().getKey() == x) {
			// System.out.println(x+" ketemu.");
			return hasil;
		} else {
			// System.out.println(x+" tidak ketemu.");
			return null;
		}
	}

	public boolean isExist(int y) {
		Node hasil = trace(y);
		if (hasil.getSubLeft().getKey() == y
				|| hasil.getSubRight().getKey() == y) {
			// System.out.println(x+" ketemu.");
			return true;
		} else {
			// System.out.println(x+" tidak ketemu.");
			return false;
		}
	}

	/**
	 * comparing 3 value (x, left_val of node y and right_val of node y), the
	 * smallest value will be returned
	 * 
	 * @param x
	 *            value that will be inserted and compared to the values in the
	 *            node
	 * @param y
	 *            node that will be compared with the new value to find smallest
	 *            value
	 * @return smallest value
	 */
	public int findSmallValue(int x, Node y) {
		int value = 0;
		if (x < y.getSubLeft().getKey()) {
			value = x;
		} else {
			value = y.getSubLeft().getKey();
		}
		return value;
	}

	/**
	 * comparing 3 value (x, left_val of node y and right_val of node y), the
	 * middle value will be returned
	 * 
	 * @param x
	 *            value that will be inserted and compared to the values in the
	 *            node
	 * @param y
	 *            node that will be compared with the new value to find middle
	 *            value
	 * @return middle value
	 */
	public int findMiddleValue(int x, Node y) {
		int value = 0;
		if (x < y.getSubLeft().getKey()) {
			value = y.getSubLeft().getKey();
		} else if (x < y.getSubRight().getKey()) {
			value = x;
		} else {
			value = y.getSubRight().getKey();
		}
		return value;
	}

	/**
	 * comparing 3 value (x, left_val of node y and right_val of node y), the
	 * biggest value will be returned
	 * 
	 * @param x
	 *            value that will be inserted and compared to the values in the
	 *            node
	 * @param y
	 *            node that will be compared with the new value to find biggest
	 *            value
	 * @return biggest value
	 */
	public int findBigValue(int x, Node y) {
		int value = 0;
		if (x > y.getSubRight().getKey()) {
			value = x;
		} else {
			value = y.getSubRight().getKey();
		}
		return value;
	}

	/**
	 * Insert value to the tree. If the x exist : update posting list, if not
	 * find the best place and do balancing Inserted value will be started from
	 * the leaf
	 * 
	 * @param x
	 *            value that will be inserted in the tree
	 */
	public void insert(int x, int idDoc) {
		Node tujuan = trace(x);
		if (tujuan.getSubLeft().getKey() == x
				|| (tujuan.getSubRight() != null && tujuan.getSubRight()
						.getKey() == x)) { // if the x has been existed ->
											// update posting list
			if (tujuan.getSubLeft().getKey() == x) {
				tujuan.getSubLeft().addIdDoc(idDoc);
			} else {
				tujuan.getSubRight().addIdDoc(idDoc);
			}
		} else {
			this.jumVal++;
			if (!tujuan.isFull()) { // if the leaf empty, x can be directly
									// insert to the leaf
				tujuan.setSubNode(new SubNode(x, idDoc));
			} else { // the leaf full -> do balancing
				Node masuk = new Node(new SubNode(x, idDoc));
				balance(tujuan, masuk);
			}
		}
	}

	/**
	 * Balance the tree
	 * 
	 * @param tujuan
	 *            Existing node
	 * @param masuk
	 *            new node that will be inserted
	 */
	public void balance(Node parent, Node masuk) {
		// System.out.println();
		// System.out.println("yang dimasukin : "+masuk.getSubLeft().getKey());
		Node gp = new Node(null); // grand parent -> if there is one value be
									// kicked will be the parent for the others
									// two values

		// this looping will stop until : pointer in root or parent that picked
		// not full or stack is empty
		// System.out.println("Size of stack : "+stack.size());
		while (!stack.isEmpty() && parent.isFull() && parent != getRoot()) {
			// System.out.println("looping");
			gp = new Node(null); // refresh grand parent
			//
			// int parentRight =
			// (parent.getSubRight()!=null)?parent.getSubRight().getKey():0;
			// System.out.println("parent : "+parent.getSubLeft().getKey()+","+parentRight);
			//
			// int masukRight =
			// (masuk.getSubRight()!=null)?masuk.getSubRight().getKey():0;
			// System.out.println("masuk : "+masuk.getSubLeft().getKey()+","+masukRight);
			if (masuk.getSubLeft().getKey() < parent.getSubLeft().getKey()) { // case4
																				// :
																				// parent
																				// full,
																				// new
																				// value
																				// that
																				// will
																				// be
																				// inserted
																				// is
																				// the
																				// smallest
																				// System.out.println("case a");
				gp.setSubLeft(parent.getSubLeft());
				parent.setSubLeft(parent.getSubRight());
				parent.setSubRight(null);
				parent.setNode_left(parent.getNode_middle());
				parent.setNode_middle(parent.getNode_right());
				parent.setNode_right(null);
				gp.setNode_left(masuk);
				gp.setNode_middle(parent);
			} else if (masuk.getSubLeft().getKey() < parent.getSubRight()
					.getKey()) { // case5 : parent full, new value that will be
									// inserted is the middle value
									// System.out.println("case b");
				gp = masuk;
				Node sibling_parent = new Node(parent.getSubRight());
				sibling_parent.setNode_left(gp.getNode_middle());
				sibling_parent.setNode_middle(parent.getNode_right());
				parent.setNode_middle(gp.getNode_left());
				parent.setSubRight(null);
				parent.setNode_right(null);
				gp.setNode_left(parent);
				gp.setNode_middle(sibling_parent);

				// int gpRight =
				// (gp.getSubRight()!=null)?gp.getSubRight().getKey():0;
				// System.out.println("gp : "+gp.getSubLeft().getKey()+","+gpRight);
				//
				// int gpAnakKiriRight =
				// (gp.getNode_left().getSubRight()!=null)?gp.getNode_left().getSubRight().getKey():0;
				// System.out.println("anak kiri gp : "+gp.getNode_left().getSubLeft().getKey()+","+gpAnakKiriRight);
				//
				// int gpAnakKananRight =
				// (gp.getNode_middle().getSubRight()!=null)?gp.getNode_middle().getSubRight().getKey():0;
				// System.out.println("anak kanan gp : "+gp.getNode_middle().getSubLeft().getKey()+","+gpAnakKananRight);
			} else if (masuk.getSubLeft().getKey() > parent.getSubRight()
					.getKey()) { // case6 : parent full, new value that will be
									// inserted is the biggest
									// System.out.println("case c");
				gp.setSubLeft(parent.getSubRight());
				parent.setNode_right(null);
				parent.setSubRight(null);
				gp.setNode_left(parent);
				gp.setNode_middle(masuk);
			}

			// int gpRight =
			// (gp.getSubRight()!=null)?gp.getSubRight().getKey():0;
			// System.out.println("gp : "+gp.getSubLeft().getKey()+","+gpRight);
			//
			// int anakKiriGpRight =
			// (gp.getNode_left().getSubRight()!=null)?gp.getNode_left().getSubRight().getKey():0;
			// System.out.println("anak kiri gp : "+gp.getNode_left().getSubLeft().getKey()+","+anakKiriGpRight);
			//
			// int anakTengahGpRight =
			// (gp.getNode_middle().getSubRight()!=null)?gp.getNode_middle().getSubRight().getKey():0;
			// System.out.println("anak tengah gp : "+gp.getNode_middle().getSubLeft().getKey()+","+anakTengahGpRight);
			parent = stack.pop();
			masuk = gp;
		}

		// int parentRight =
		// (parent.getSubRight()!=null)?parent.getSubRight().getKey():0;
		// System.out.println("parent : "+parent.getSubLeft().getKey()+","+parentRight);
		//
		// int masukRight =
		// (masuk.getSubRight()!=null)?masuk.getSubRight().getKey():0;
		// System.out.println("masuk : "+masuk.getSubLeft().getKey()+","+masukRight);

		gp = new Node(null); // refresh grand parent
		if (parent.getSubRight() == null) { // root empty
			if (masuk.getSubLeft().getKey() < parent.getSubLeft().getKey()) { // case2
																				// :
																				// parent
																				// (root)
																				// empty,
																				// new
																				// value
																				// that
																				// will
																				// be
																				// inserted
																				// is
																				// smaller
																				// System.out.println("case e");

				parent.setSubRight(parent.getSubLeft());
				parent.setNode_right(parent.getNode_middle());
				parent.setSubLeft(masuk.getSubLeft());
				parent.setNode_left(masuk.getNode_left());
				parent.setNode_middle(masuk.getNode_middle());

				// parentRight =
				// (parent.getSubRight()!=null)?parent.getSubRight().getKey():0;
				// System.out.println("parent : "+parent.getSubLeft().getKey()+","+parentRight);
				//
				// masukRight =
				// (masuk.getSubRight()!=null)?masuk.getSubRight().getKey():0;
				// System.out.println("masuk : "+masuk.getSubLeft().getKey()+","+masukRight);

			} else if (masuk.getSubLeft().getKey() > parent.getSubLeft()
					.getKey()) { // case3 : parent (root) empty, new value that
									// will be inserted is bigger
									// System.out.println("case f");
				parent.setSubRight(masuk.getSubLeft());
				parent.setNode_middle(masuk.getNode_left());
				parent.setNode_right(masuk.getNode_middle());
			}
		} else { // root not empty
			if (masuk.getSubLeft().getKey() < parent.getSubLeft().getKey()) { // parent
																				// (root)
																				// full,
																				// new
																				// value
																				// that
																				// will
																				// be
																				// inserted
																				// is
																				// the
																				// smallest
																				// System.out.println("case h");
				gp.setSubLeft(parent.getSubLeft());
				setRoot(gp);
				parent.setSubLeft(parent.getSubRight());
				parent.setSubRight(null);
				parent.setNode_left(parent.getNode_middle());
				parent.setNode_middle(parent.getNode_right());
				parent.setNode_right(null);
				gp.setNode_left(masuk);
				gp.setNode_middle(parent);
			} else if (masuk.getSubLeft().getKey() < parent.getSubRight()
					.getKey()) { // parent (root) full, new value that will be
									// inserted is the middle value
									// System.out.println("case i");
				gp.setSubLeft(parent.getSubRight());
				gp.setNode_left(masuk.getNode_middle());
				gp.setNode_middle(parent.getNode_right());
				parent.setNode_middle(masuk.getNode_left());
				parent.setNode_right(null);
				parent.setSubRight(null);
				setRoot(masuk);
				root.setNode_left(parent);
				root.setNode_middle(gp);
			} else if (masuk.getSubLeft().getKey() > parent.getSubRight()
					.getKey()) { // parent (root) full, new value that will be
									// inserted is the biggest
									// System.out.println("case j");
				gp.setSubLeft(parent.getSubRight());
				setRoot(gp);
				parent.setNode_right(null);
				parent.setSubRight(null);
				gp.setNode_left(parent);
				gp.setNode_middle(masuk);
			}
		}
		System.out.println();
	}

	/**
	 * printing the tree and all the value consisted
	 * 
	 * @param tree
	 *            that will be printed
	 */
	public void print(Node tree) {
		if (tree != null) {
			System.out.print(tree.getSubLeft().getKey() + "|");

			int treeRight = (tree.getSubRight() != null) ? tree.getSubRight()
					.getKey() : 0;
			System.out.print(treeRight);
			System.out.print(' ');

			print(tree.getNode_left());

			print(tree.getNode_middle());

			print(tree.getNode_right());
		}
	}

	public void print2(Node tree) {
		if (tree != null) {
			tree.getSubLeft().printSubNode();
			System.out.print("|");

			if (tree.getSubRight() != null) {
				tree.getSubRight().printSubNode();
				System.out.print(' ');
			} else {
				System.out.print("null ");
			}

			System.out.println();
			print2(tree.getNode_left());

			print2(tree.getNode_middle());

			print2(tree.getNode_right());

		}

	}

	/**
	 * saving tree as an object in a file
	 * 
	 * @param ob
	 *            name of the object
	 * @param namaFile
	 *            name of the file
	 */
	public static void save(Object ob, String namaFile) {
		// System.out.println("--> Saving object...");
		try {
			FileOutputStream f_out = new FileOutputStream(namaFile);
			ObjectOutputStream obj_out = new ObjectOutputStream(f_out);
			obj_out.writeObject(ob);
		} catch (Exception e) {
			System.out.println(e.toString());
			System.exit(1);
		}
	}

	/**
	 * load file that consist tree object
	 * 
	 * @param namaFile
	 *            name of the file that will be loaded
	 * @return tree object
	 */
	public static Object load(String namaFile) {
		Object ob = new Object();
		// System.out.println("--> Loading saved object...");
		try {
			FileInputStream f_in = new FileInputStream(namaFile);
			ObjectInputStream obj_in = new ObjectInputStream(f_in);
			ob = obj_in.readObject();
		} catch (Exception e) {
			System.out.println(e.toString());
			System.exit(1);
		}
		return ob;
	}

	/**
	 * 
	 public void MakeKamus(){ try { Class.forName("com.mysql.jdbc.Driver");
	 * Connection connection = DriverManager.getConnection(
	 * "jdbc:mysql://localhost/finalproject_web?user=root"); Statement statement
	 * = connection.createStatement(); ResultSet result =
	 * statement.executeQuery("select kata from token"); ScapegoatTree tree =
	 * new ScapegoatTree(); while(result.next()){
	 * tree.insert(result.getString("kata").hashCode()); }
	 * 
	 * Helper.save(tree, "kamus_bahasa_indonesia.sgt"); } catch (SQLException e)
	 * { // TODO Auto-generated catch block e.printStackTrace(); } catch
	 * (ClassNotFoundException e) { // TODO Auto-generated catch block
	 * e.printStackTrace(); } }
	 */

}